package jzoffer;

/**
 * Author:   dengxin
 * Date:     2020/6/17 5:08 下午
 * 矩形覆盖：可以用2*1的小矩形横着或者竖着覆盖更大的矩形
 * 那么用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法
 * 思路：递归
 * 1、2*n的矩形可以由一个竖着的2*1的矩形和一个2*(n-1)的矩形组成
 * 2、2*n的矩形可以由两个横着的2*1的矩形和一个2*(n-1)的矩形组成
 *
 */
public class jz10 {

    public static void main(String[] args) {
        System.out.println(rectCover(5));
    }

    public static int rectCover(int target) {
        if (target == 1) {
            return 1;
        }
        if (target == 2) {
            return 2;
        }
        int one = 1,  two = 2;
        int result = 0;
        for (int i = 3; i<=target; i++) {
            result = one + two;
            one = two;
            two = result;
        }
        return result;
    }
}
